package 力扣日常刷题.木22一月.第05天0113;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/13
 * @description
 */
public class Demo05回溯中等子集 {

    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(nums,0,new ArrayList<>());
        return ans;
    }

    void  dfs(int[] nums,int index, ArrayList<Integer> list){
        if(index == nums.length){
            ans.add(new ArrayList<>(list));
            return;
        }
        list.add(nums[index]);
        dfs(nums,index+1,list);
        list.remove(list.size()-1);
        while(index < nums.length-1 && nums[index] == nums[index +1]){
            // 去重，不选当前数递归时直接跳过重复数
            // 所有重复数的可能性在前面递归中均会出现
            index++;
        }
        dfs(nums,index +1 ,list);
    }



}
